package DP.Medium;

import java.util.Arrays;

public class LC0516 {
    int[][] dp; // dp[i,j]表示[i,j]范围内的最长回文子序列
    char[] charArray;

    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        charArray = s.toCharArray();
        dp = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);
        for (int i = 0; i < n; i++) dp[i][i] = 1;

        return dp(0, n - 1);
    }

    private int dp(int i, int j) {
        if (dp[i][j] != -1) return dp[i][j];
        // 在下面的过程中，i≠j


        if (charArray[i] == charArray[j]) {
            if (j - i < 2) { // 其实就是j=i+1
                dp[i][j] = charArray[i] == charArray[j] ? 2 : 1;
            }
            else dp[i][j] = dp(i + 1, j - 1) + 2;
        }
        else {
            // 无需针对i和j的关系再做判断，因为i和j不相等时，j≥i+1，i或j向对方移动一个单位距离不会交叉
            dp[i][j] = Math.max(dp(i + 1, j), dp(i, j - 1));
        }

        return dp[i][j];
    }

    public static void main(String[] args) {
        String s = "bbbab";
        LC0516 solver = new LC0516();
        System.out.println(solver.longestPalindromeSubseq(s));
    }
}
